62. 不同路径

Similar Question

Solution Tips

方案一: 图论 Dfs

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。

方案二: 动态规划

var uniquePaths = function(m, n) {
    // 1. dp[i][j] 代表到达当前位置的可能 path 数量
    // 因为只有两个方向可以走, 往右走, 就等于左边的格子的 path
    // 往下走就等于上面的格子的 path
    // 2. dp[i][j] = dp[i -1][j] + dp[i][j - 1]
    // 3. dp[0][0] = 1
    // dp[1][0] = 1
    // dp[0][1] = 1
    // 4. 从左到右, 从上到下即可
    // 这一题感觉通项公式是最简单的
    const dp = Array(m).fill().map(item => Array(n))

    for (let i = 0; i < m; ++i) {
        dp[i][0] = 1
    }

    for (let i = 0; i < n; ++i) {
        dp[0][i] = 1
    }

    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

滚动数组优化

var uniquePaths = function(m, n) {
    let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
    // dp[i][j] 表示到达（i，j） 点的路径数
    for (let i=1; i<m; i++) {
        for (let j=1; j< n;j++) {
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];

};

方案三: 数论 - 组合

var uniquePaths = function(m, n) {
    let ans = 1;
    for (let x = n, y = 1; y < m; ++x, ++y) {
        ans = Math.floor(ans * x / y);
    }
    return ans;
};